/**
 * 面试题56-2：数组中唯一只出现一次的数字
 */
public class Offer_56_II {
    /**
     * 遍历统计
     * <p>
     * 如果一个数字出现三次，那么它二进制每一位也出现三次。
     * 
     * 如果把所有出现三次的数字的二进制每一位都分别加起来，那么每一位的和都能被 3 整除。
     * 
     * 如果某一位的和能被 3 整除，那么那个只出现一次的数字的二进制那一位就是 0，否则就是 1。
     */
    public int singleNumber(int[] nums) {
        // 整数 32 位，统计每一位上 1 的个数
        int[] counts = new int[32];
        for (int num : nums) {
            int bitMask = 1;
            // 从最低位开始，将每一位与 1 进行与运算
            for (int i = 31; i >= 0; i--) {
                int bit = num & bitMask;
                if (bit != 0) {
                    counts[i] += 1;
                }
                bitMask <<= 1;
            }
        }

        int ans = 0;
        for (int i = 0; i < 32; i++) {
            ans <<= 1;
            ans += counts[i] % 3;
        }
        return ans;
    }
}
